// Package _2_在一个二叉树中找节点的后继节点 main
// @Title _2_在一个二叉树中找节点的后继节点
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-01-16 16:35
// @Create  2022-01-16 16:35
package main

// 比普通的二叉树节点类型多了一个指向父节点的指针，头结点的parent指向nil
type Node struct {
	Val    int
	Left   *Node
	Right  *Node
	Parent *Node
}

//返回后继节点的意思就是中序遍历后的节点 但是没必要每次都中序遍历啊

func findBackNode(root *Node) *Node {
	if root == nil {
		return nil
	}
	//1. x 有右子树，那么返回右子树上的最左节点
	if root.Right != nil {
		return getLeftMost(root.Right)
	} else {
		//2. x 没有右子树，往上找 找到第一个是左子树的父亲节点，如果都不满足，返回nil
		parent := root.Parent
		for parent != nil && parent.Left != root {
			{
				root = parent
				parent = root.Parent
			}
		}
		return parent
	}
}

func getLeftMost(root *Node) *Node {
	if root == nil {
		return root
	}
	for root.Left != nil {
		root = root.Left
	}
	return root
}
